#include <iostream>

// 节点结构
template <class T>
struct ListNode {
    T data;
    ListNode* next;
    ListNode* prev;
    
    ListNode(const T& val = T()) : data(val), next(nullptr), prev(nullptr) {}
};

// 迭代器类
template <class T>
class ListIterator {
public:
    using value_type = T;
    using pointer = T*;
    using reference = T&;
    
    ListNode<T>* node;
    ListNode<T>* head;  // 添加头节点指针以检测循环
    
    ListIterator(ListNode<T>* x = nullptr, ListNode<T>* h = nullptr) 
        : node(x), head(h) {}
    
    reference operator*() const { return node->data; }
    pointer operator->() const { return &(operator*()); }
    
    ListIterator& operator++() {
        node = node->next;
        if (node == head) {  // 如果到达头节点，返回nullptr表示结束
            node = nullptr;
        }
        return *this;
    }
    
    ListIterator operator++(int) {
        ListIterator tmp = *this;
        ++(*this);
        return tmp;
    }
    
    ListIterator& operator--() {
        if (node == nullptr) {  // 如果是end()迭代器
            node = head->prev;
        } else {
            node = node->prev;
        }
        return *this;
    }
    
    ListIterator operator--(int) {
        ListIterator tmp = *this;
        --(*this);
        return tmp;
    }
    
    bool operator==(const ListIterator& x) const { return node == x.node; }
    bool operator!=(const ListIterator& x) const { return node != x.node; }
};

// List类
template <class T>
class List {
private:
    ListNode<T>* head;
    size_t size_;
    
public:
    using iterator = ListIterator<T>;
    using value_type = T;
    using reference = T&;
    using const_reference = const T&;
    using size_type = size_t;
    
    // 构造函数
    List() : head(nullptr), size_(0) {}
    
    // 析构函数
    ~List() {
        clear();
    }
    
    // 迭代器相关
    iterator begin() { return iterator(head, head); }
    iterator end() { return iterator(nullptr, head); }
    
    // 容量相关
    bool empty() const { return size_ == 0; }
    size_type size() const { return size_; }
    
    // 元素访问
    reference front() { return head->data; }
    reference back() { return head->prev->data; }
    
    // 修改器
    void push_front(const T& value) {
        ListNode<T>* new_node = new ListNode<T>(value);
        if (empty()) {
            head = new_node;
            head->next = head;
            head->prev = head;
        } else {
            new_node->next = head;
            new_node->prev = head->prev;
            head->prev->next = new_node;
            head->prev = new_node;
            head = new_node;
        }
        ++size_;
    }
    
    void push_back(const T& value) {
        ListNode<T>* new_node = new ListNode<T>(value);
        if (empty()) {
            head = new_node;
            head->next = head;
            head->prev = head;
        } else {
            new_node->next = head;
            new_node->prev = head->prev;
            head->prev->next = new_node;
            head->prev = new_node;
        }
        ++size_;
    }
    
    void pop_front() {
        if (empty()) return;
        if (size_ == 1) {
            delete head;
            head = nullptr;
        } else {
            ListNode<T>* old_head = head;
            head = head->next;
            head->prev = old_head->prev;
            old_head->prev->next = head;
            delete old_head;
        }
        --size_;
    }
    
    void pop_back() {
        if (empty()) return;
        if (size_ == 1) {
            delete head;
            head = nullptr;
        } else {
            ListNode<T>* old_tail = head->prev;
            old_tail->prev->next = head;
            head->prev = old_tail->prev;
            delete old_tail;
        }
        --size_;
    }
    
    void clear() {
        while (!empty()) {
            pop_front();
        }
    }
};

// 测试代码
int main() {
    List<int> myList;
    
    // 测试push_back
    myList.push_back(1);
    myList.push_back(2);
    myList.push_back(3);
    
    // 测试迭代器
    std::cout << "List contents: ";
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 测试front和back
    std::cout << "Front: " << myList.front() << std::endl;
    std::cout << "Back: " << myList.back() << std::endl;
    
    // 测试pop_front
    myList.pop_front();
    std::cout << "After pop_front: ";
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    // 测试pop_back
    myList.pop_back();
    std::cout << "After pop_back: ";
    for (auto it = myList.begin(); it != myList.end(); ++it) {
        std::cout << *it << " ";
    }
    std::cout << std::endl;
    
    return 0;
}
